package wh.相交链表;

import java.util.HashSet;
import java.util.Set;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/1/9 13:47
 * @description:
 * @version:
 */
public class Solution {
    public static void main(String[] args) {

    }

    //哈希集合
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode l1 = headA;
        ListNode l2 = headB;
        Set<ListNode> set = new HashSet<>();
        while (l1 != null){
            set.add(l1);
            l1 = l1.next;
        }
        while (l2 != null){
            if (!set.add(l2)){
                return l2;
            }
            l2 = l2.next;
        }
        return null;
    }

    //双指针
    public static ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}
